package everyday;

import java.util.Arrays;
import java.util.*;
public class T1000 {
    static final int INF = 0x3f3f3f3f;
    int[][][] d;
    int[] sum;
    int k;

    public int mergeStones(int[] stones, int k) {
        int len = stones.length;
        if ((len - 1) % (k - 1) != 0) return -1;
        d = new int[len][len][k + 1];
        this.k = k;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                Arrays.fill(d[i][j], -1);
            }
            d[i][i][1] = 0;
        }
        sum = new int[len + 1];
        for (int i = 1; i < len + 1; i++) {
            sum[i] = sum[i - 1] + stones[i - 1];
        }
        return get(0, len - 1, 1);
    }

    public int get(int l, int r, int n) {
        if (d[l][r][n] != -1) return d[l][r][n];
        if (n > r - l + 1) return INF;
        if (n==1){
            int res=get(l,r,k);
            if (res==INF)return d[l][r][1]=INF;
            d[l][r][1]=res+sum[r+1]-sum[l];
            return d[l][r][1];
        }

        int min=INF;
        for (int p = l; p <r ; p+=(k-1)) {
            min=Math.min(min,get(l,p,1)+get(p+1,r,n-1));
        }
        return d[l][r][n]=min;
    }
}
